/* Copyright  2009-2010
   @Author
   Richard Changde Yin            e-mail yinchangde@hotmail.com

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/**
 * @filename: index.h
 */
#ifndef __SQL_INDEX_H__
#define __SQL_INDEX_H__

#include <global.h>
#include <error.h>
#include <common.h>
#include <debug.h>

#include <mem_field.h>
#include <mutex.h>
#include <util.h>

#define FIX_LENGTH(cs, pos, length, char_length)                        \
  do {                                                                  \
    if (length > char_length)                                           \
      char_length= my_charpos(cs, pos, pos+length, char_length);        \
    set_if_smaller(char_length,length);                                 \
  } while(0)

/** A Enum value
*/
enum IndexType
{
    hashIndex = 0,    /**<hash index>*/
    treeIndex,        /**<tree index>*/
    unknownIndex      /**<no index>*/
};
class BucketTree;
class Chunk;
class Database;
class Transaction;
class Table ;
class CINDEX;


class HashIndexNode
{
    HashIndexNode& operator = (const HashIndexNode&);
    HashIndexNode (const HashIndexNode&);
    HashIndexNode (HashIndexNode&);
public:
    HashIndexNode():ptrToKey_(0),
                    ptrToTuple_(0),
                    prev(0),
                    next_(0)
    {}
    void* ptrToKey_;
    void* ptrToTuple_;
    HashIndexNode *prev;
    HashIndexNode *next_;
};

class IndexInfo;
class TreeNode
{
public:
    TreeNode(){ }
    Mutex mutex_;
    void *min_;
    void *max_;
    int noElements_;
    int balance_;
    TreeNode *next_;
    TreeNode *prev_;
    //Note::after this array of pointer to tuples are stored

    BackEnd::DbRetVal insert(Database *db, IndexInfo *info,
                             void *indexPtr, void *tuple);
    BackEnd::DbRetVal insert(int position, Database *db,
                             IndexInfo *indInfo,
                             CINDEX *iptr, void *tuple,
                             TreeNode *iter);
    BackEnd::DbRetVal remove(Database *db, IndexInfo *info,
                             void *indexPtr, void *tuple);
    BackEnd::DbRetVal update(Database *db, IndexInfo *info,
                             void *indexPtr, void *tuple);
    void displayAll(IndexInfo *indInfo, void *indexPtr);
    void displayAll(int offset);
};

class BucketIter
{
    HashIndexNode *iter;
    HashIndexNode *head;
    BucketIter& operator= (BucketIter& );
    BucketIter (BucketIter& );
    BucketIter (const BucketIter& );
public:
    BucketIter():iter(0),head(0){}
    BucketIter(HashIndexNode *_head) { iter = head = _head;}
    HashIndexNode* next();
    inline void reset() { iter = head; }
    friend class BucketList;
};
class BucketList
{
private:
    HashIndexNode *head;
    HashIndexNode *tail;
    uint32_t      _size;
    BucketList& operator =(BucketList& );
    BucketList(BucketList&);
    BucketList(const BucketList&);
public:
    BucketList():head(0),tail(0),_size(0){}
    BucketList(HashIndexNode *h){ head = h; }
    inline void *getBucketListHead(){ return head;}
    inline void *getBucketListTail(){ return tail;}
    BackEnd::DbRetVal insert(Chunk *chunk, Database *db, void *key, void *tuple);
    BackEnd::DbRetVal insertNode(HashIndexNode *node);
    BackEnd::DbRetVal removeNode(Chunk *chunk, Database *db,HashIndexNode *thenode);
    BackEnd::DbRetVal remove(Chunk *chunk, Database *db, void *key);
    inline uint32_t getSize(){
      return _size ;
    }
    inline void init()
    {
      head=0;tail=0;_size=0;
    }
    void removeHead(Chunk *chunk, Database *db);
    void removeAll (Chunk *chunk, Database *db);
    inline BucketIter getIterator()
    {
        BucketIter it(head);
        return it;
    }
    inline void setTail(HashIndexNode* _tail){
      tail= _tail;
    }
    inline void setHead(HashIndexNode* _head){
      head = _head ;
    }
};

#include <my_alloc.h>
#include <rb_tree.h>

enum search_element_result_type{
  get_key = 0,
  get_element
};

enum key_allocate_type {
  allocate_bychunk = 0,
  assignment
};
struct bucket_tree_arg{
  void* tupleptr  ;
  void* keyptr    ;
  uint32_t key_length;
  uint32_t search_flag;
  IndexInfo* info ;
  Chunk* chunkptr ;
  Database* dbptr ;
  enum search_element_result_type  search_type;
  enum key_allocate_type   alloc_type ;

};

typedef struct bucket_tree_arg BKT_TREE_ARG ;


class BUCKET_TREE_ELEMENT {
public:
  BUCKET_TREE_ELEMENT *left;
  BUCKET_TREE_ELEMENT *right;
  void * hashbucketList_    ;
  BucketList*    bucketList_;
  Chunk* key_chunk ;
  void * key_ptr        ;
  uint32_t count:31,
           colour:1;        /* black is marked as 1 */
} ;
#define BUCKET_ELEMENT_CHILD(element, offs) (*(BUCKET_TREE_ELEMENT**)((char*)element + offs))
class BucketTree
{
    void delete_tree_element     (BUCKET_TREE_ELEMENT *);
    int tree_walk_left_root_right(BUCKET_TREE_ELEMENT *,
                                  tree_walk_action,void *);
    int tree_walk_right_root_left(BUCKET_TREE_ELEMENT *,
                                  tree_walk_action,void *);
    void left_rotate (BUCKET_TREE_ELEMENT **parent,BUCKET_TREE_ELEMENT *leaf);
    void right_rotate(BUCKET_TREE_ELEMENT **parent, BUCKET_TREE_ELEMENT *leaf);
    void rb_insert   (BUCKET_TREE_ELEMENT ***parent,
                      BUCKET_TREE_ELEMENT *leaf);
    void rb_delete_fixup(BUCKET_TREE_ELEMENT ***parent);

    bool mb_isInit   ;
    uint32_t flag    ;
    inline void* get_element_key(BUCKET_TREE_ELEMENT* element)
    {
       return element->key_ptr;
    }
public:
    BUCKET_TREE_ELEMENT *root,null_element;
    BUCKET_TREE_ELEMENT **parents[MAX_TREE_HEIGHT];
    uint32_t offset_to_key,elements_in_tree,size_of_element;
    uint32_t allocated;
    qsort_cmp2 compare;
    void *custom_arg;
    void *hashNodechunk ;
    BucketTree():root(0)
    {
        offset_to_key=elements_in_tree=size_of_element=0;
        allocated  = 0 ;
        custom_arg = 0 ;
        hashNodechunk  = 0 ;
        mb_isInit= false;
    }
    inline void setFlag(uint32_t _flag)
    {
      flag = _flag ;
    }

    inline uint32_t getTreeFlag(){
      return flag ;
    }
      /* Functions on whole tree */
    void init_tree(uint32_t default_alloc_size,
                   int size,
                   qsort_cmp2 compare,
                   void* custom_arg );
    void delete_tree();

    /* Functions on leafs */
    BUCKET_TREE_ELEMENT *tree_insert(void *key,
                              uint32_t key_size,
                              void *custom_arg,
                              int&  rv);
    void* tree_search    (void *key, void *custom_arg);
    int   tree_walk      (tree_walk_action action,void *argument,
                          TREE_WALK visit);
    int   tree_delete    (void *key, uint32_t key_size, void *custom_arg);
    void *tree_search_key(const void *key,BUCKET_TREE_ELEMENT **parents,
                           BUCKET_TREE_ELEMENT ***last_pos,
                            enum ha_rkey_function flag, void *custom_arg);
    void *tree_search_edge( BUCKET_TREE_ELEMENT **parents,
                            BUCKET_TREE_ELEMENT ***last_pos, int child_offs);
    void *tree_search_next( BUCKET_TREE_ELEMENT ***last_pos, int l_offs,
                            int r_offs);
    ha_rows tree_record_pos (const void *key,
                             enum ha_rkey_function search_flag,
                             void *custom_arg);
    void free_tree( myf free_flags);
};

class Bucket
{

public:
    Mutex mutex_;
    Chunk *element_chunk;
    void* bucketList_;
    BucketTree subtree;
    pthread_rwlock_t rwlock;
};
class HashIndex;
class IndexInfo;
class HashIndexInfo;
class TreeIndex;
class Index
{
    // create (one) object for each indexing mechanisms here
    // Also need to make changes to getIndex() and destroy() methods
    // accordingly for new index mechanism.
    static HashIndex *hIdx;
    static TreeIndex *tIdx;
    static uint32_t usageCount;
    Index& operator =(Index&);
    Index(const Index&);
    Index(Index&);
public:
    Index(){}
    virtual ~Index(){}
    static Index* getIndex(IndexType type);
    static void init()   ;
    static void destroy();

    virtual BackEnd::DbRetVal insert(Table *tbl, Transaction *tr,
                                     void *indexPtr, IndexInfo *info,
                                     void *tuple, bool undoFlag)=0;
    virtual BackEnd::DbRetVal remove(Table *tbl, Transaction *tr,
                                      void *indexPtr, IndexInfo *info,
                                      void *tuple,
                                      void *recpos,bool undoFlag)=0;
    virtual BackEnd::DbRetVal update(Table *tbl, Transaction *tr,
                                      void *indexPtr, IndexInfo *info,
                                      void *tuple, bool undoFlag)=0;
    static int mm_key_cmp(register IndexInfo *info,
                          register unsigned char *a,register unsigned char *b,
                          uint32_t key_length, uint32_t nextflag,
                          uint32_t *diff_pos);
    static int keys_compare(void* param,
                            const void *key1,const void *key2);

};
class HashIndex : public Index
{

public:
    BackEnd::DbRetVal insert(Table *tbl, Transaction *tr,
                             void *indexPtr, IndexInfo *info,
                             void *tuple, bool undoFlag);
    BackEnd::DbRetVal remove(Table *tbl, Transaction *tr,
                             void *indexPtr, IndexInfo *info,
                             void *tuple, void* recpos,bool undoFlag);
    BackEnd::DbRetVal update(Table *tbl, Transaction *tr,
                             void *indexPtr, IndexInfo *info,
                             void *tuple, bool undoFlag);

    static uint32_t rec_hashnr  (HashIndexInfo *info,
                                 register const unsigned char *rec)   ;

    static uint32_t make_rb_key(IndexInfo *info, unsigned char *key,
                                 const unsigned char *rec);

    static uint32_t rb_pack_key(IndexInfo *info, unsigned char *key,
                                   const unsigned char *old,
                                   key_part_map keypart_map);

    static int      rec_key_cmp (HashIndexInfo *info,
                                 const unsigned char *tuple1,
                                 const unsigned char *tuple2,
                                 bool diff_if_only_endspace_difference)   ;

    static uint32_t cal_rec_key_hash(unsigned char* start,uint32_t len);

    static BackEnd::DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
    static BackEnd::DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
};

class TreeIndex : public Index
{

    TreeNode*   locateNode(TreeNode *iter, void *tuple, IndexInfo *indInfo);
    BackEnd::DbRetVal removeElement(Database *db, TreeNode *iter,
                           void *tuple, HashIndexInfo *info);
public:
    BackEnd::DbRetVal insert(Table *tbl, Transaction *tr,
                   void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
    BackEnd::DbRetVal remove(Table *tbl, Transaction *tr,
                   void *indexPtr, IndexInfo *info, void *tuple, void* recpos,
                   bool undoFlag);
    BackEnd::DbRetVal update(Table *tbl, Transaction *tr,
                   void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);

};
class TreeIter
{
    TreeNode *iter;
    TreeNode *head;
    int fldOffset;
    //DataType type;
    enum_field_types type ;

    int length;
    //ComparisionOp op;
    bool asc;
    void *searchKey;
    bool firstCall;
    int nodeOffset;
    bool recordsOver;

    void* locateNode();
    void* locateElement();

public:
    TreeIter(){}
    TreeIter(TreeNode *hd) { iter = head = hd;
                             firstCall = true;
                             recordsOver=false;}
    void setFldOffset(int off) { fldOffset = off; }
    void setTypeLength(enum_field_types t, int l) { type =t ; length =l; }
    void* prev();
    void* next();
    void  nextNode();
    void* getFirstElement();
    void* getLastElement();
    void reset() { iter = head; firstCall = true; recordsOver=false; }
};

enum IndexIntType
{
     hashOneField = 1,
     hash         = 2,
     tree         = 3
};

class IndexInfo
{
    IndexInfo& operator= (IndexInfo& idxinfo);
    IndexInfo(IndexInfo& idxinfo);
    IndexInfo(const IndexInfo& idxinfo);
public:
    /**tablename**/
    char tableName[IDENTIFIER_LENGTH];
    char idxName  [IDENTIFIER_LENGTH];

    IndexType indType    ;

    IndexInfo *parent    ;

    uint32_t flag;            /* HA_NOSAME | HA_NULL_PART_KEY */

    uint16_t fieldnr;   /* Fieldnum in UNIREG (1,2,3,...) */
    /*the field offset*/
    uint32_t  fldOffset;
    /* Length of key part in bytes, excluding NULL flag and length bytes */

    uint32_t  null_pos;    /* position to NULL indicator */
    uint16_t  bit_pos ;    /* Position to bit part */
    uint8_t   null_bit;
    uint16_t  length  ;
    uint32_t  start   ;
    uint8_t   ha_type;  /* Type of key (for sort) */
    bool      isUnique;
    bool      isPrimary;
    uint8_t   bit_start;/* if bit field */
    unsigned char *indexPtr;
    BackEnd::List<IndexInfo> sublist  ;

    const CHARSET_INFO *charset;

    IndexInfo():parent (0),
                fieldnr(0),
                fldOffset(-1),
                length(0),
                start(0),
                charset(0)


    {
      memset(tableName,0,IDENTIFIER_LENGTH);
      memset(idxName,0,IDENTIFIER_LENGTH);
      isUnique = false ;
      isPrimary= false  ;
      bit_start = 0;
      indexPtr  = 0;
    }

    virtual ~IndexInfo() {}
};


class HashIndexInfo :public IndexInfo
{
    HashIndexInfo& operator = (HashIndexInfo& );
    HashIndexInfo(HashIndexInfo&);
    HashIndexInfo(const HashIndexInfo&);
public:

    size_t  noOfBuckets;

    Bucket* buckets;

    //DataType type;
    enum_field_types type ;

    inline void print()
    {
    }

    HashIndexInfo():noOfBuckets(109),
                    buckets(0)   /*  the prt to buckets*/

    {
        indType = hashIndex ;
    }

    ~HashIndexInfo() {

    }
};
#endif //__SQL_INDEX_H__

